package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午7:40:34
*/
public class Q62 {
    /** 
     *@param A : an integer rotated sorted array
     *@param target :  an integer to be searched
     *return : an integer
     */
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        int mid = findMin(A);
        int rs = searchRight(A, 0, mid, target);
        if (rs == -1) {
            rs = searchRight(A, mid, A.length - 1, target);
        }
        return rs;
    }

    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int point = -1;
        while (left <= right) {
            point = (left + right) / 2;
            if (nums[left] > nums[right]) {// 旋转排序
                if (nums[point] >= nums[left]) {
                    left = point + 1;
                } else {
                    right = point;
                }
            } else {// 正确的排序
                return left;
            }

        }
        return point;
    }

    private int searchRight(int[] A, int left, int right, int target) {
        while (left <= right) {
            int point = (left + right) / 2;
            if (A[point] > target) {
                right = point - 1;
            } else if (A[point] == target) {
                return point;
            } else {
                left = point + 1;
            }
        }
        return -1;
    }

    @Test
    public void testA() {
        int A[] = {1, 1, 2, 3, 4, 5, 1 };
        System.out.println(search(A, 2));
    }
}
